{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #相交链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getIntersectionNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相交链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个单链表的头节点&nbsp;<code>headA</code> 和 <code>headB</code> ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 <code>null</code> 。</p>\n",
    "\n",
    "<p>图示两个链表在节点 <code>c1</code> 开始相交<strong>：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png\" style=\"height: 130px; width: 400px;\" /></a></p>\n",
    "\n",
    "<p>题目数据 <strong>保证</strong> 整个链式结构中不存在环。</p>\n",
    "\n",
    "<p><strong>注意</strong>，函数返回结果后，链表必须 <strong>保持其原始结构</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_1.png\" style=\"height: 130px; width: 400px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3\n",
    "<strong>输出：</strong>Intersected at &#39;8&#39;\n",
    "<strong>解释：</strong>相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。\n",
    "从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。\n",
    "在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_2.png\" style=\"height: 136px; width: 350px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal&nbsp;= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1\n",
    "<strong>输出：</strong>Intersected at &#39;2&#39;\n",
    "<strong>解释：</strong>相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。\n",
    "从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。\n",
    "在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<p><a href=\"https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png\" target=\"_blank\"><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png\" style=\"height: 126px; width: 200px;\" /></a></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2\n",
    "<strong>输出：</strong>null\n",
    "<strong>解释：</strong>从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。\n",
    "由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。\n",
    "这两个链表不相交，因此返回 null 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>listA</code> 中节点数目为 <code>m</code></li>\n",
    "\t<li><code>listB</code> 中节点数目为 <code>n</code></li>\n",
    "\t<li><code>0 &lt;= m, n &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= skipA &lt;= m</code></li>\n",
    "\t<li><code>0 &lt;= skipB &lt;= n</code></li>\n",
    "\t<li>如果 <code>listA</code> 和 <code>listB</code> 没有交点，<code>intersectVal</code> 为 <code>0</code></li>\n",
    "\t<li>如果 <code>listA</code> 和 <code>listB</code> 有交点，<code>intersectVal == listA[skipA + 1] == listB[skipB + 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>能否设计一个时间复杂度 <code>O(n)</code> 、仅用 <code>O(1)</code> 内存的解决方案？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 160&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/intersection-of-two-linked-lists/\">https://leetcode-cn.com/problems/intersection-of-two-linked-lists/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3u1WK4](https://leetcode.cn/problems/3u1WK4/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3u1WK4](https://leetcode.cn/problems/3u1WK4/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8\\n[4,1,8,4,5]\\n[5,6,1,8,4,5]\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        pa = headA\n",
    "        pb = headB\n",
    "        while pa != pb:\n",
    "            pa = headB if pa is None else pa.next\n",
    "            pb = headA if pb is None else pb.next\n",
    "        return pa\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a, b = headA, headB\n",
    "        while a and b and a != b:\n",
    "            a = a.next\n",
    "            b = b.next\n",
    "        if a == b:\n",
    "            return a\n",
    "        if b == None:\n",
    "            headA, headB = headB, headA\n",
    "            a, b = b, a\n",
    "        a = headB\n",
    "        while a and b:\n",
    "            a = a.next\n",
    "            b = b.next\n",
    "        b = headA\n",
    "        while a and b:\n",
    "            if a == b:\n",
    "                return a\n",
    "            a = a.next\n",
    "            b = b.next\n",
    "        return None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        nodeDic = set()\n",
    "        while headA:\n",
    "            nodeDic.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in nodeDic:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # write code here\n",
    "        #在遇到你之前，我们是两条平行线，从不期待着与谁的交汇\n",
    "        you, me = headA,headB\n",
    "        #兜兜转转，我们的轨迹终将与共\n",
    "        while you!=me:\n",
    "            #我们携手，即使短暂掉队，等待会重新拉上彼此\n",
    "            you = you.next if you else headB\n",
    "            me = me.next if me else headA\n",
    "        #在世纪的终末，你也是一切的答案\n",
    "        return you\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        node_temp = set()\n",
    "        p = headA\n",
    "        while(p):\n",
    "            node_temp.add(p)\n",
    "            p = p.next\n",
    "        p = headB\n",
    "        while(p):\n",
    "            if(p in node_temp):\n",
    "                return p\n",
    "            p = p.next\n",
    "        return None "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A,B = headA,headB\n",
    "        while A != B:\n",
    "            A = A.next if A else headB\n",
    "            B = B.next if B else headA\n",
    "        return A\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        t_a, t_b = headA, headB\n",
    "        flag1, flag2 = False, False\n",
    "        while t_a!=t_b:\n",
    "            if t_a.next == None:\n",
    "                if flag1: return None\n",
    "                flag1 = True\n",
    "                t_a = headB\n",
    "            else:\n",
    "                t_a = t_a.next\n",
    "            if t_b.next == None:\n",
    "                if flag2: return None\n",
    "                flag2 = True\n",
    "                t_b = headA\n",
    "            else:\n",
    "                t_b = t_b.next\n",
    "        \n",
    "        return t_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1 = headA\n",
    "        p2 = headB\n",
    "        while p1 != p2:\n",
    "            if p1:\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                p1 = headB\n",
    "\n",
    "            if p2:\n",
    "                p2 = p2.next\n",
    "            else:\n",
    "                p2 = headA\n",
    "\n",
    "            \n",
    "        return p1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？\n",
    "# 要求空间复杂度是o(1)，这就需要原地修改\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc\n",
    "\n",
    "# 如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。\n",
    "# 解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。\n",
    "# 所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。\n",
    "class Solution:\n",
    "     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "        while p1 != p2:\n",
    "            if p1:\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                p1 = headB\n",
    "\n",
    "            if p2:\n",
    "                p2 = p2.next\n",
    "            else:\n",
    "                p2 = headA\n",
    "\n",
    "        return p1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        p1, p2 = headA, headB\n",
    "        while p1 != p2:\n",
    "            if p1 is None:\n",
    "                p1 = headB\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "            if p2 is None:\n",
    "                p2 = headA\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "        return p1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return \n",
    "        pointA = headA\n",
    "        pointB = headB\n",
    "        while pointA != pointB:\n",
    "            if pointA:\n",
    "                pointA = pointA.next\n",
    "            else: pointA = headB\n",
    "            if pointB:\n",
    "                pointB = pointB.next\n",
    "            else: pointB = headA\n",
    "        return pointA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        pA, pB = headA, headB\n",
    "        falg = False\n",
    "        while True:\n",
    "            if not pA:\n",
    "                if falg:\n",
    "                    break\n",
    "                falg = True\n",
    "                pA = headB\n",
    "            if not pB:\n",
    "                pB = headA\n",
    "            if pA and pA == pB:\n",
    "                return pA\n",
    "            pA = pA.next\n",
    "            pB = pB.next\n",
    "        return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p=headA\n",
    "        b=headB\n",
    "        t=0\n",
    "        m=[]\n",
    "        while p !=b and t<2:\n",
    "            \n",
    "            p=p.next\n",
    "            b=b.next\n",
    "            \n",
    "            if p is None:\n",
    "                p=headB\n",
    "                t+=1\n",
    "            if b is None:\n",
    "                b=headA\n",
    "        if t==2:\n",
    "            return None\n",
    "        return p\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a, b = headA, headB\n",
    "        while a != b:\n",
    "            a = a.next if a else headB\n",
    "            b = b.next if b else headA\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "        while p1 != p2:\n",
    "            p1 = p1.next if p1 else headB\n",
    "            p2 = p2.next if p2 else headA\n",
    "\n",
    "        return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1 = headA\n",
    "        p2 = headB\n",
    "        while p1 != p2:\n",
    "            \n",
    "            if p1 is None:\n",
    "                p1 = headB\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "            if p2 is None:\n",
    "                p2 = headA\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "        return p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return \n",
    "        node1, node2 = headA, headB\n",
    "        while node1 != node2:\n",
    "            node1 = node1.next if node1 else headB\n",
    "            node2 = node2.next if node2 else headA\n",
    "        return node1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def len_list(self, headA):\n",
    "        length = 0\n",
    "        while headA:\n",
    "            length +=1\n",
    "            headA = headA.next\n",
    "        return length\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        ha, hb = headA, headB\n",
    "        len_a = self.len_list(ha)\n",
    "        len_b = self.len_list(hb)\n",
    "        while len_a != len_b:\n",
    "            if len_a > len_b:\n",
    "                headA = headA.next\n",
    "                len_a -=1\n",
    "            else:\n",
    "                headB = headB.next\n",
    "                len_b -=1\n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "        while p1!=p2:\n",
    "            if p1:\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                p1 = headB\n",
    "            if p2:\n",
    "                p2 = p2.next\n",
    "            else:\n",
    "                p2 = headA\n",
    "        return p1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not (headA and headB):\n",
    "            return None\n",
    "\n",
    "        p,q=headA,headB\n",
    "        # tmp=None\n",
    "        while headA!=headB:\n",
    "            if headA:\n",
    "                headA=headA.next\n",
    "            else:\n",
    "                # if tmp:\n",
    "                #     if tmp!=headA:\n",
    "                #         return None\n",
    "                # else:\n",
    "                #     tmp=headA\n",
    "                headA=q\n",
    "\n",
    "            if headB:\n",
    "                headB=headB.next\n",
    "            else:\n",
    "                # if tmp:\n",
    "                #     if tmp!=headB:\n",
    "                #         return None\n",
    "                # else:\n",
    "                #     tmp=headB\n",
    "                headB=p\n",
    "\n",
    "        return headA\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 分别计算链表长度\n",
    "        def getLen(node):\n",
    "            size = 0\n",
    "            curr = node\n",
    "            while curr:\n",
    "                size += 1\n",
    "                curr = curr.next\n",
    "            return size\n",
    "        \n",
    "        lenA = getLen(headA)\n",
    "        lenB = getLen(headB)\n",
    "\n",
    "        # 长的先行\n",
    "        a = headA\n",
    "        b = headB\n",
    "\n",
    "        diff = lenA - lenB\n",
    "        step = diff if diff >= 0 else -diff\n",
    "        \n",
    "        while step > 0:\n",
    "            if diff > 0:\n",
    "                a = a.next if a else None\n",
    "            else:\n",
    "                b = b.next if b else None\n",
    "            step -= 1\n",
    "        \n",
    "        # 寻找交点\n",
    "        while a and b:\n",
    "            if a is b:\n",
    "                return a\n",
    "            a = a.next\n",
    "            b = b.next\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        visited = []\n",
    "        while headA:\n",
    "            visited.append(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB not in visited:\n",
    "                headB = headB.next\n",
    "            else:\n",
    "                return headB\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "\n",
    "        A,B = headA,headB\n",
    "\n",
    "        while A!=B:\n",
    "            if A:\n",
    "                A = A.next\n",
    "            else:\n",
    "                A = headB\n",
    "            \n",
    "            if B:\n",
    "                B = B.next\n",
    "            else:\n",
    "                B = headA\n",
    "        \n",
    "        return A\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        l1 = headA\n",
    "        l2 = headB\n",
    "        while l1 != l2:\n",
    "            if l1 is None:\n",
    "                l1 = headB\n",
    "            else:\n",
    "                l1 = l1.next\n",
    "            if l2 is None:\n",
    "                l2 = headA\n",
    "            else:\n",
    "                l2 = l2.next\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        #---- 走过相同路程\n",
    "        a = headA\n",
    "        b = headB\n",
    "        while a != b:\n",
    "            a = a.next if a else headB\n",
    "            b = b.next if b else headA\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        curr1 = headA\n",
    "        curr2 = headB\n",
    "        while curr1 != curr2:\n",
    "            if not curr1:\n",
    "                curr1 = headB\n",
    "            else:\n",
    "                curr1 = curr1.next\n",
    "            if not curr2:\n",
    "                curr2 = headA\n",
    "            else:\n",
    "                curr2 = curr2.next\n",
    "        return curr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1 = headA\n",
    "        p2 = headB\n",
    "        while p1!=p2:\n",
    "            if p1 == None:\n",
    "                p1 = headB\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "\n",
    "            if p2 == None:\n",
    "                p2 = headA\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "        return p1\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        nodeA, nodeB = headA, headB\n",
    "        while nodeA or nodeB:\n",
    "            if nodeA == nodeB:\n",
    "                return nodeA\n",
    "            if nodeA:\n",
    "                nodeA = nodeA.next\n",
    "            else:\n",
    "                nodeA = headB\n",
    "            if nodeB:\n",
    "                nodeB = nodeB.next\n",
    "            else:\n",
    "                nodeB = headA\n",
    "        return\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a=headA;b=headB\n",
    "        if (headA or headB) is None:\n",
    "            return null\n",
    "        else:\n",
    "            while a!=b:\n",
    "                a = headB if a is None else a.next\n",
    "                b = headA if b is None else b.next\n",
    "            return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a_cnt, b_cnt = 0, 0\n",
    "        p = headA\n",
    "        while p is not None:\n",
    "            a_cnt += 1\n",
    "            p = p.next\n",
    "        p = headB\n",
    "        while p is not None:\n",
    "            b_cnt += 1\n",
    "            p = p.next\n",
    "\n",
    "        if a_cnt > b_cnt:\n",
    "            p1, p2, diff_cnt = headA, headB, a_cnt - b_cnt\n",
    "        else:\n",
    "            p1, p2, diff_cnt = headB, headA, b_cnt - a_cnt\n",
    "\n",
    "        for i in range(diff_cnt):\n",
    "            p1 = p1.next\n",
    "\n",
    "        while p1 is not None and p2 is not None:\n",
    "            if p1 == p2:\n",
    "                return p1\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "        while p1 != p2:\n",
    "            if not p1:\n",
    "                p1 = headB\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "            if not p2:\n",
    "                p2 = headA\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "        return p1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "        A=headA\n",
    "        B=headB\n",
    "        while A!=B:\n",
    "            if A:\n",
    "                A=A.next\n",
    "            else:\n",
    "                A=headB\n",
    "            if B:\n",
    "                B=B.next\n",
    "            else:\n",
    "                B=headA\n",
    "\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        h1, h2 = headA, headB\n",
    "        while h1 != h2:\n",
    "            h1 = h1.next if h1 else headB\n",
    "            h2 = h2.next if h2 else headA\n",
    "        return h1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "        A=headA\n",
    "        B=headB\n",
    "        while A!=B:\n",
    "            if A:\n",
    "                A=A.next\n",
    "            else:\n",
    "                A=headB\n",
    "            if B:\n",
    "                B=B.next\n",
    "            else:\n",
    "                B=headA\n",
    "        if A is None and B is None:\n",
    "            return None\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a, b = headA, headB\n",
    "        while a!=b:\n",
    "            a = a.next if a else headB\n",
    "            b = b.next if b else headA\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A,B=headA,headB\n",
    "        while A!=B:\n",
    "            if A:\n",
    "                A=A.next\n",
    "            else:\n",
    "                A=headB\n",
    "            if B:\n",
    "                B=B.next\n",
    "            else:\n",
    "                B=headA\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        l,r=headA,headB\n",
    "        while l != r:\n",
    "            if l:\n",
    "                l=l.next\n",
    "            else:\n",
    "                l=headB\n",
    "            if r:\n",
    "                r=r.next\n",
    "            else:\n",
    "                r=headA\n",
    "        return l        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "      \n",
    "        listA = []\n",
    "\n",
    "        while headA:\n",
    "          listA.append(headA)\n",
    "          headA = headA.next\n",
    "        \n",
    "        while headB:\n",
    "            if headB in listA:\n",
    "                return headB\n",
    "            else:\n",
    "                headB = headB.next\n",
    "            \n",
    "        return None\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "\n",
    "        x, y = headA, headB\n",
    "\n",
    "        while x != y:\n",
    "\n",
    "            x = x.next if x else headB\n",
    "\n",
    "            y = y.next if y else headA\n",
    "\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    # 1.\n",
    "    # def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "    #     node1 = headA\n",
    "    #     node2 = headB\n",
    "    #     # 先分别遍历看节点个数\n",
    "    #     na, nb = 0, 0\n",
    "    #     while node1:\n",
    "    #         node1 = node1.next\n",
    "    #         na += 1\n",
    "    #     while node2:\n",
    "    #         node2 = node2.next\n",
    "    #         nb += 1\n",
    "    #     # 更长的一方先走abs(na - nb)\n",
    "    #     node1 = headA\n",
    "    #     node2 = headB\n",
    "    #     while na > nb:\n",
    "    #         node1 = node1.next\n",
    "    #         na -= 1\n",
    "    #     while na < nb:\n",
    "    #         node2 = node2.next\n",
    "    #         nb -= 1\n",
    "    #     # 在一个起跑线上遍历，第一个相等的节点就是\n",
    "    #     while node1 and node2:\n",
    "    #         print(node1.val, node2.val)\n",
    "    #         if node1 is node2:\n",
    "    #             return node1\n",
    "    #         node1 = node1.next\n",
    "    #         node2 = node2.next\n",
    "    #     return None\n",
    "    \n",
    "    # 2.双指针，每个指针都走完a+b+c相遇即可\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        pA = headA\n",
    "        pB = headB\n",
    "        while pA != pB:\n",
    "            pA = pA.next if pA is not None else headB\n",
    "            pB = pB.next if pB is not None else headA\n",
    "\n",
    "        return pA\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        ListNodeA = headA\n",
    "        ListNodeB = headB\n",
    "\n",
    "        while(ListNodeA != ListNodeB):\n",
    "            ListNodeA = ListNodeA.next if ListNodeA != None else headB\n",
    "            ListNodeB = ListNodeB.next if ListNodeB != None else headA\n",
    "\n",
    "        return ListNodeA\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:return None\n",
    "        a,b = headA,headB\n",
    "        while a!=b:\n",
    "            a = a.next if a else headB\n",
    "            b = b.next if b else headA\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1=headA\n",
    "        p2=headB\n",
    "        listA=[]\n",
    "        while p1 is not None:\n",
    "            listA.append(p1)\n",
    "            p1=p1.next\n",
    "        while p2 is not None:\n",
    "            if p2 not in listA:\n",
    "                p2=p2.next\n",
    "            else:\n",
    "                return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\n",
    "def get_size(head: ListNode) -> int:\n",
    "    size = 0\n",
    "    while head:\n",
    "        head = head.next\n",
    "        size += 1\n",
    "    return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        size_l = [get_size(headA), get_size(headB)]\n",
    "        preA, preB = ListNode(next=headA), ListNode(next=headB)\n",
    "        if size_l[0] == size_l[1]:\n",
    "            pass\n",
    "        elif size_l[0] > size_l[1]:\n",
    "            for _ in range(size_l[0] - size_l[1]):\n",
    "                preA = preA.next\n",
    "        else:\n",
    "            for _ in range(size_l[1] - size_l[0]):\n",
    "                preB = preB.next\n",
    "        while preA.next:\n",
    "            if preA.next == preB.next:\n",
    "                return preA.next\n",
    "            else:\n",
    "                preA = preA.next\n",
    "                preB = preB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？\n",
    "# 要求空间复杂度是o(1)，这就需要原地修改\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc\n",
    "\n",
    "# 如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。\n",
    "# 解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。\n",
    "# 所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。\n",
    "class Solution:\n",
    "     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "        while p1 != p2:\n",
    "            if p1:\n",
    "                p1 = p1.next\n",
    "            else:\n",
    "                p1 = headB\n",
    "\n",
    "            if p2:\n",
    "                p2 = p2.next\n",
    "            else:\n",
    "                p2 = headA\n",
    "\n",
    "        return p1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        slow, fast = headA, headB\n",
    "        while slow or fast:\n",
    "            if slow == fast:\n",
    "                return slow\n",
    "            slow = slow.next if slow else headB\n",
    "            fast = fast.next if fast else headA\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \n",
    "        if not headA or not headB: return None\n",
    "        haset = []\n",
    "        while headA:\n",
    "            haset.append(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in haset:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        tmp1,tmp2 = headA,headB\n",
    "        len1,len2 = 0,0 \n",
    "        while tmp1.next is not None:\n",
    "            tmp1 = tmp1.next\n",
    "            len1 += 1\n",
    "        while tmp2.next is not None:\n",
    "            tmp2 = tmp2.next\n",
    "            len2 += 1\n",
    "        tmp1,tmp2 = headA,headB\n",
    "        if len1 < len2:\n",
    "            len1,len2 = len2,len1\n",
    "            tmp1,tmp2 = tmp2,tmp1\n",
    "        more = len1-len2\n",
    "        for i in range(more):\n",
    "            tmp1 = tmp1.next\n",
    "        while tmp1.next != None:\n",
    "            if tmp1 == tmp2:\n",
    "                break\n",
    "            tmp1 = tmp1.next\n",
    "            tmp2 = tmp2.next\n",
    "        if tmp1 == tmp2:\n",
    "            return tmp1\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \n",
    "        def getl(h):\n",
    "            res = 0\n",
    "            while h:\n",
    "                res += 1\n",
    "                h = h.next\n",
    "            return res\n",
    "        def move(h, c):\n",
    "            for i in range(c):\n",
    "                h = h.next\n",
    "            return h\n",
    "        la = getl(headA)\n",
    "        lb = getl(headB)\n",
    "        qa = move(headA, la-lb if la >= lb else 0)\n",
    "        qb = move(headB, lb-la if la < lb else 0)\n",
    "        while qa and qb:\n",
    "            if qa == qb:\n",
    "                return qa\n",
    "            qa = qa.next\n",
    "            qb = qb.next\n",
    "        return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "        # x, y = headA, headB\n",
    "        # while x != y:\n",
    "        #     x = x.next if x else headB\n",
    "        #     y = y.next if y else headA\n",
    "        # return x\n",
    "\n",
    "        d = {}\n",
    "        while headA:\n",
    "            d[headA] = headA\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if d.get(headB):\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None\n",
    "\n",
    "#不太对 需要存节点headA，而不是值headA.val\n",
    "        # lst = list()\n",
    "        # while headA:\n",
    "        #     lst.append(headA)\n",
    "        #     headA = headA.next\n",
    "        # while headB:\n",
    "        #     if headB in lst:\n",
    "        #         return headB\n",
    "        #     headB = headB.next\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "        zidian={}\n",
    "        A=headA\n",
    "        B=headB\n",
    "        while A:\n",
    "            zidian[A]=A.val\n",
    "            A=A.next\n",
    "        while B:\n",
    "            if zidian.get(B):\n",
    "                return B\n",
    "            B=B.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return \n",
    "        node1, node2 = headA, headB\n",
    "        while node1 != node2:\n",
    "            node1 = node1.next if node1 else headB\n",
    "            node2 = node2.next if node2 else headA\n",
    "        return node1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        heada = headA\n",
    "        headb = headB\n",
    "        if headA == None or headB == None:\n",
    "            return None\n",
    "        while heada != headb:\n",
    "            if heada:\n",
    "                heada = heada.next\n",
    "            else:\n",
    "                heada = headB\n",
    "            if headb:\n",
    "                headb = headb.next\n",
    "            else:\n",
    "                headb = headA\n",
    "        return heada\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "\n",
    "        a=headA\n",
    "        b=headB\n",
    "        while a != b:\n",
    "            a = a.next if a else headB\n",
    "            b = b.next if b else headA\n",
    "        return a\n",
    "\n",
    "        # while a is not b:\n",
    "        #     if a :\n",
    "        #         a=a.next\n",
    "        #     else:\n",
    "        #         a=headB\n",
    "\n",
    "        #     if b :\n",
    "        #         b=b.next\n",
    "        #     else:\n",
    "        #         b=headA\n",
    "\n",
    "        #     return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        d = {}\n",
    "        while headA:\n",
    "            d[headA] = headA\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if d.get(headB):\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        node1 = headA\n",
    "        node2 = headB\n",
    "        # 先分别遍历看节点个数\n",
    "        na, nb = 0, 0\n",
    "        while node1:\n",
    "            node1 = node1.next\n",
    "            na += 1\n",
    "        while node2:\n",
    "            node2 = node2.next\n",
    "            nb += 1\n",
    "        # print(na, nb)\n",
    "        # 更长的一方先走abs(na - nb)\n",
    "        node1 = headA\n",
    "        node2 = headB\n",
    "        while na > nb:\n",
    "            node1 = node1.next\n",
    "            na -= 1\n",
    "        while na < nb:\n",
    "            node2 = node2.next\n",
    "            nb -= 1\n",
    "        # 在一个起跑线上遍历，第一个相等的节点就是\n",
    "        while node1 and node2:\n",
    "            print(node1.val, node2.val)\n",
    "            if node1 is node2:\n",
    "                return node1\n",
    "            node1 = node1.next\n",
    "            node2 = node2.next\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return\n",
    "        \n",
    "        curA = headA\n",
    "        curB = headB\n",
    "        \n",
    "        while curA != curB:\n",
    "            curA = curA.next if curA else headB\n",
    "            curB = curB.next if curB else headA\n",
    "        return curA\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "        :type head1, head1: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dic = dict()\n",
    "        cur = headA\n",
    "        if cur == None:\n",
    "            return headB\n",
    "        while cur != None:\n",
    "            dic[cur] = 1\n",
    "            cur = cur.next\n",
    "        cur = headB\n",
    "        while cur != None:\n",
    "            if cur in dic:\n",
    "                return cur  \n",
    "            cur = cur.next  \n",
    "        else:    \n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p1, p2 = headA, headB\n",
    "\n",
    "        while p1 != p2:\n",
    "            if p1 == None:\n",
    "                p1 = headB\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "            if p2 == None:\n",
    "                p2 = headA\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "\n",
    "        return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headB or not headA:\n",
    "            return\n",
    "        pa,pb=headA,headB\n",
    "        while pa!=pb:\n",
    "            pa=headB if not pa else pa.next\n",
    "            pb=headA if not pb else pb.next\n",
    "        return pa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        A,B = headA,headB\n",
    "        while A != B:\n",
    "            A = A.next if A else headB\n",
    "            B = B.next if B else headA\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 相交的起始节点，必须是相交节点后的节点都一样吗？ 只找到第一个相遇的节点就好\n",
    "        # 输出相交节点的值\n",
    "        if not headA or not headB: # 只要有一个为空\n",
    "            return None\n",
    "        # A和B值之间长度的缺口部分，如果能补齐，则第一个相等的节点就是相交节点；\n",
    "        # 根据A追B的解决方法，较长的要比较短的多跑缺口部分，较长的跑到shorter的开头部分时，较短的刚好跑完缺口部分；\n",
    "        \n",
    "        # p1 = headA\n",
    "        # p2 = headB\n",
    "        # n = 0\n",
    "        # while(p1 != p2): # 为什么p1.next != p2.next 不能通过\n",
    "        #     if n == 2:\n",
    "        #         return None\n",
    "        #     if not p1.next: # 如果p1到最后一个结点\n",
    "        #         p1 = headB\n",
    "        #         n += 1\n",
    "        #     if not p2.next:\n",
    "        #         p2 = headA\n",
    "        #     p1 = p1.next\n",
    "        #     p2 = p2.next\n",
    "        # return p1\n",
    "\n",
    "        x, y = headA, headB\n",
    "        while x != y:\n",
    "            x = x.next if x else headB\n",
    "            y = y.next if y else headA\n",
    "        return x\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        h = {}\n",
    "        if (not headA) or (not headB):\n",
    "            return None\n",
    "        \n",
    "        current = headA\n",
    "        while current:\n",
    "            h[id(current)]=current.val\n",
    "            current = current.next\n",
    "\n",
    "        current = headB\n",
    "        while current:\n",
    "            try:\n",
    "                if h[id(current)]:\n",
    "                    print('return')\n",
    "                    return current\n",
    "            except:\n",
    "                pass\n",
    "            current = current.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        a = set()\n",
    "        while headA:\n",
    "            a.add(headA)\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if headB in a:\n",
    "                return headB\n",
    "            headB = headB.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        flag1 = headA\n",
    "        flag2 = headB\n",
    "        while flag1 != flag2:\n",
    "            flag1 = flag1.next if flag1 else headB\n",
    "            flag2 = flag2.next if flag2 else headA\n",
    "        return flag1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        def getLenth(head):\n",
    "            ans = 0\n",
    "            while head:\n",
    "                ans += 1\n",
    "                head = head.next\n",
    "            return ans\n",
    "        \n",
    "        lenA = getLenth(headA)\n",
    "        lenB = getLenth(headB)\n",
    "        if lenA > lenB:\n",
    "            n = lenA - lenB\n",
    "            for i in range(n):\n",
    "                headA = headA.next\n",
    "        else:\n",
    "            n = lenB-lenA\n",
    "            for i in range(n):\n",
    "                headB = headB.next\n",
    "\n",
    "        while headA and headB:\n",
    "            if headA == headB:\n",
    "                return headA\n",
    "            else:\n",
    "                headA =headA.next\n",
    "                headB = headB.next\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 在遇到你之前,我们是俩条平行线,以外不会相遇\n",
    "        you = headA\n",
    "        me = headB\n",
    "        # 兜兜转转,我们的生命轨迹终将出现交点\n",
    "        while you!=me:\n",
    "            # 我们携手与共,即使一个人掉队,也会拉上彼此继续前行\n",
    "            you = you.next if you else headB\n",
    "            me = me.next if me else headA\n",
    "            # 往后余生,你就是我的世界\n",
    "        return you\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        p = headA\n",
    "        q = headB\n",
    "        # 如果不相交\n",
    "        while(p != q):\n",
    "            if p:\n",
    "                p = p.next\n",
    "            else:\n",
    "                p = headB\n",
    "            if q:\n",
    "                q = q.next\n",
    "            else:\n",
    "                q = headA\n",
    "        if p == q:\n",
    "            return p\n",
    "        else:\n",
    "            return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        d={}\n",
    "        while headA:\n",
    "            d[headA]=headA\n",
    "            headA=headA.next\n",
    "        while headB:\n",
    "            if d.get(headB):\n",
    "                return headB\n",
    "            headB=headB.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if not headA or not headB:\n",
    "            return None\n",
    "        \n",
    "        ALen = 0\n",
    "        cur = headA\n",
    "        while cur:\n",
    "            ALen += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        BLen = 0\n",
    "        cur = headB\n",
    "        while cur:\n",
    "            BLen += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        if ALen > BLen:\n",
    "            dist = ALen - BLen\n",
    "            \n",
    "            curA = headA\n",
    "            while dist > 0:\n",
    "                curA = curA.next\n",
    "                dist -= 1\n",
    "            curB = headB\n",
    "        else:\n",
    "            dist = BLen - ALen\n",
    "\n",
    "            curB = headB\n",
    "            while dist > 0:\n",
    "                curB = curB.next\n",
    "                dist -= 1\n",
    "            curA = headA\n",
    "        \n",
    "        while curA and curB:\n",
    "            if curA == curB:\n",
    "                return curA\n",
    "            curA = curA.next\n",
    "            curB = curB.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA is None or headB is None:\n",
    "            return None\n",
    "        p1 = headA\n",
    "        p2 = headB\n",
    "        while p1 != p2:\n",
    "            p1 = p1.next if p1 else headB\n",
    "            p2 = p2.next if p2 else headA\n",
    "        return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        if headA == None or headB == None:\n",
    "            return None\n",
    "        a = {}\n",
    "        while headA:\n",
    "            a[headA] = headA.val\n",
    "            headA = headA.next\n",
    "        while headB:\n",
    "            if a.get(headB):\n",
    "                return headB\n",
    "            headB =headB.next\n",
    "        return None  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        # 法1 双哈希表\n",
    "        # 法二 o(n)\n",
    "        x,y = headA,headB\n",
    "        while x != y:\n",
    "            x = x.next if x else headB\n",
    "            y = y.next if y else headA\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        curA = headA\n",
    "        dic = set()\n",
    "        while curA:\n",
    "            dic.add(curA)\n",
    "            curA = curA.next\n",
    "        # print(dic)\n",
    "        curB = headB\n",
    "        while curB:\n",
    "            if curB in dic:\n",
    "                return curB\n",
    "            curB = curB.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        pa,pb = headA,headB\n",
    "        while not pa == pb:\n",
    "            pa = pa.next if pa else headB\n",
    "            pb = pb.next if pb else headA\n",
    "        return pa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        result={}\n",
    "        while headA:\n",
    "            result[headA]=headA\n",
    "            headA=headA.next\n",
    "        while headB:\n",
    "            for i in result:\n",
    "                if i == headB:\n",
    "                    return headB\n",
    "            headB=headB.next\n",
    "        return None\n",
    "                \n",
    "     \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        seen=set()\n",
    "        while headA:\n",
    "            seen.add(headA)\n",
    "            headA=headA.next\n",
    "        while headB:\n",
    "            if headB in seen:\n",
    "                return headB\n",
    "            headB=headB.next\n",
    "        return  None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        len_a = 0\n",
    "        len_b = 0\n",
    "        temp_a = headA\n",
    "        temp_b = headB\n",
    "        while temp_a:\n",
    "            len_a += 1\n",
    "            temp_a = temp_a.next\n",
    "        while temp_b:\n",
    "            len_b += 1\n",
    "            temp_b = temp_b.next\n",
    "        # 长的链表头节点往后移动len_长-len_短\n",
    "        while len_a > len_b:\n",
    "            headA = headA.next\n",
    "            len_a -= 1\n",
    "        while len_b > len_a:\n",
    "            headB = headB.next\n",
    "            len_b -= 1\n",
    "        while headA and headB and headA != headB:\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "        return headA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p = headA\n",
    "        q = headB\n",
    "        d = {}\n",
    "        while p:\n",
    "            d[p] = 0\n",
    "            p = p.next\n",
    "        while q:\n",
    "            if q in d:\n",
    "                return q\n",
    "            q = q.next\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:\n",
    "        p, q = headA, headB\n",
    "        res = []\n",
    "        res2 = set()\n",
    "        while p:\n",
    "            # res.append(p)\n",
    "            res2.add(p)\n",
    "            p = p.next\n",
    "        while q:\n",
    "            if q in res2:\n",
    "                return q\n",
    "            q = q.next\n",
    "        return None\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
